/*
 * meituan.com Inc.
 * Copyright (c) 2010-2018 All Rights Reserved.
 */
package item21;

import org.junit.Test;

import java.util.Arrays;

/**
 * <p>
 *
 * </p>
 * @author LvJing
 * @version $Id:ReOrderArr.java v1.0 2018/7/29 下午10:59 LvJing Exp $
 */
public class ReOrderArr {

    /**
     * 题目21：输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，
     * 并保证奇数和奇数，偶数和偶数之间的相对位置不变。（与书上的题目要求多了个调整后保持排序）
     * 思路：2种思路，一种是排序但时间复杂度为O(n^2)，一种是空间换时间，时间复杂度为O(n)
     * 排序思路为用i从头遍历数组直到找到第一个偶数，j=i+1开始遍历直到找到第一个奇数，把i到j-1（均为偶数）之间的数后移，i的位置则为奇数。
     * 空间换时间的思路比较有意思也很简单，新建一个同等大小数组，从头开始遍历数组，奇数筛选出来放入新数组，第二次遍历筛选偶数。
     */
    class Solution {

        public void reOrderArray(int[] array) {
            if (array == null || array.length == 0 || array.length == 1) {
                return;
            }

            int length = array.length;
            int i = 0;
            while (i < length) {
                // 直到找到第一个偶数
                while (i < length && array[i] % 2 == 1) {
                    i++;
                }
                int j = i + 1;
                // 直到找到第一个奇数
                while (j < length && array[j] % 2 == 0) {
                    j++;
                }
                if (j < length) {
                    int temp = array[j];// 待前移的奇数
                    for (int k = j - 1; k >= i; k--) {
                        array[k + 1] = array[k];
                    }
                    array[i++] = temp;
                } else {
                    break;
                }
            }
        }

        public void reOrderArray2(int[] array) {
            if (array == null || array.length == 0 || array.length == 1) {
                return;
            }

            int length = array.length;
            int[] copyArr = new int[length];
            int index = 0;

            for (int i = 0; i < length; i++) {
                if (array[i] % 2 == 1) {
                    copyArr[index++] = array[i];
                }
            }

            for (int i = 0; i < length; i++) {
                if (array[i] % 2 == 0) {
                    copyArr[index++] = array[i];
                }
            }
            System.arraycopy(copyArr, 0, array, 0, length);
        }
    }

    @Test
    public void test01() {
        int[] arr = {1, 2, 3, 4, 5, 6, 7};
        Solution solution = new Solution();
        solution.reOrderArray(arr);
        System.out.println(Arrays.toString(arr));
    }

    @Test
    public void test02() {
        int[] arr = {1, 2, 3, 4, 5, 6, 7};
        Solution solution = new Solution();
        solution.reOrderArray2(arr);
        System.out.println(Arrays.toString(arr));
    }
}
